Ad hoc mobile networks have been proposed as a solution to wireless networking where nodes are mobile, the range of their mobility exceeds the transmission range of any single transceiver, and there is no existing network infrastructure such as that which exists in a more traditional fixed wireless network having transmission towers and base stations. Typical proposed applications for such ad hoc networks include military command and control, search and rescue, sensor, and disaster relief networks. However, ad hoc networking may find broader application as a networking approach in offices, across college campuses, in homes, and even possibly as the architecture of a future generation of mobile wireless data networks. Indeed, the increasing availability of high frequency transceivers (i.e. high bandwidth) will allow simultaneous support of multiple connections at different qualities of service (QoS). However, the increased attenuation associated with such high frequencies will make cellular architectures centered on nodes communicating directly with base stations impractical. The natural alternative is for nodes to communicate with their peers rather than with a base station and to cooperate to support connectivity as is envisaged by the ad hoc networking approach.
Ad hoc networks have no base stations and are quite volatile. The performance of these networks is contingent on the ability of access protocols to allocate bandwidth and the ability of routing protocols to determine and to maintain routes among the nodes. Extensive research has been directed toward this issue and numerous protocols have been proposed for both medium access and routing.
Three major challenges confront ad hoc access protocols, providing fair access onto a single channel to multiple contending nodes (i.e. all contending nodes have the same opportunity to gain access), achieving spatial reuse of the channel, and providing a mechanism that allows nodes to reserve bandwidth on the single access channel.
Fair access is typically achieved either by scheduling accesses or by introducing temporal randomness so that nodes may gain access at different times. Due to the distributed nature of ad hoc networks, temporally random access techniques improving on the principles underlying the Aloha and Carrier Sense Multiple Access (CSMA) protocols have dominated.
The IEEE 802.11 and the ETSI HIPERLAN MAC protocols exemplify the state of the art in standardized protocols. The 802.11 MAC is based on a distributed CSMA like protocol that seeks to avoid collisions when the channel is congested. Nodes schedule packet transmissions to start in randomly selected time slots within a contention window. Nodes transmit the packets after sensing the channel to be idle for that selected number of time slots. If the packet is not received successfully, a back off algorithm randomly schedules retransmission in a larger contention window. The contention window increases exponentially with each failure, thus reducing the probability that nodes, which collide, will subsequently collide. However, the protocol's performance still degrades with congestion.
The HIPERLAN protocol takes a different approach. Nodes first attempt to send packets as they arrive. If a packet arrives when the channel is busy, the node waits until the channel is free again and then contends immediately using the signaling protocol Elimination Yield Non-Preemptive Multiple Access (EYNPMA). When multiple nodes within range of each other contend simultaneously, this protocol is better than 96% effective at isolating a single winner. By contrast with 802.11, the performance of this access mechanism is robust to the density of nodes however is very susceptible to hidden node effects on account the timing of EYNPMA is based on the release of the channel by a transmitter. Only nodes within range of this transmitter can achieve the appropriate synchronization.
RICH-DP offers a variation to slotted Aloha. All nodes follow a common frequency hopping sequence. Access attempts occur on these hops as in slotted aloha but they are receiver initiated. Nodes poll their peers in these hops to determine if their peer has a packet to send them. If so, the two nodes exchange data stalling at that hop frequency and thereby avoiding collisions with future polls and data exchanges, which will occur on other hop frequencies. The use of request-to-receive (RTR) messages sent by destinations results in collision avoidance as collisions occur at destinations. Unique to this approach is that not only do the access attempts occur at random times they may occur when the sources have no data to send. Nevertheless on account of a dedicated collision free channel for the subsequent data exchange and the concurrent use of multiple channels in the same space it is a very competitive protocol. Its limitations are that it is sensitive to high node densities on account of the finite number of frequencies and typical of the slotted aloha access mechanism is subject to congestion collapse as collisions may still occur in the RTR polls.
The dispersion of nodes in networks offers the potential to spatially reuse the radio channel so that more than one pair of nodes can exchange data at a time but also results in the pesky hidden node phenomena where distant nodes transmitting simultaneously unbeknownst to each other interfere at one or both destinations. The challenge to access protocols is to resolve from a spatial distribution of transmitters a set that can use the channel simultaneously without interfering with each other.
The deleterious impact of the hidden node problem is a significant issue for CSMA protocols. In fact, when “wireless” CSMA was first presented, it was noted that CSMA's performance could degrade to that of Aloha. Subsequently, it was demonstrated that a two-way handshake prior to data transmission could suppress collisions. The principle is for the source to first transmit a short “request-to-send” (RTS) packet to the destination implicitly directing all nodes within range to back off while the data exchange takes place. Upon receiving the RTS, the destination replies with a “clear-to-send” (CTS) packet, which simultaneously directs its neighbors to back off while giving the source the go-ahead to transmit the data packet. Collisions may still occur during RTS-CTS exchanges but they only interfere with these short transmissions rather than the longer data transmissions. In fact, modeling of the present invention shows that a successful RTS-CTS exchange is a sufficient condition to assure no collision in the subsequent data transmission.
The RTS-CTS exchanges are currently used by 802.11. By contrast, HIPERLAN takes a different approach in dealing with hidden nodes. A node assumes a collision has occurred when it fails to gain access but then does not detect a packet transmission. When this is the case the node identifies this as the “hidden elimination” condition and foregoes attempting to gain access for at least 500 ms. Unfortunately, various studies reveal HIPERLAN's performance degrades significantly with an increase of hidden nodes.
RICH-DP avoids the channel sharing challenge by segregating transmissions on different frequencies.
Access protocols must enable the reservation of resources if they are to achieve bandwidth or delay QoS constraints.
The 802.11 protocol supports two types of coordination functions built upon its distributed access mechanisms, a distributed coordination function (DCF) and a point coordination function (PCF). The DCF is the default. The PCF enables a central node, the point coordinator (PC), to schedule transmissions; however, the standard provides no guidance on how this should be done. The PCF can be used to support multimedia traffic in certain situations, but this assumes that all nodes are within range of the PC. In a widely distributed network, this approach would require multiple PCs working together to manage access. Currently no work attempting such a solution for an ad hoc network appears to exist. In fact, the DCF remains the predominant coordination function used in ad hoc networking. Attempts have been made to add signaling to the DCF so as to enable it to support constant bit rate services; however, this work again requires all nodes to be within range of each other. The 802.11 protocol does not simultaneously support resource reservation and spatial reuse.
HIPERLAN's method of supporting QoS is to give priority to packets based on their residual lifetime. The EYNPMA protocol has five levels of priority, all based on the residual lifetime of a packet. Unfortunately, experiments demonstrate that this priority scheme is not effective at supporting QoS since there arc no mechanisms to distinguish between packets associated with real time services and old data packets. The problem is, of course, more pronounced in congested networks where more nodes would contend to transmit old, i.e. higher priority, data packets.
Spread spectrum (SS) technology has frequently been proposed as a method to multiplex signals within the same geographic region. Spread spectrum also offers other very attractive features such as resistance to detection, resistance to multipath induced fades, and resistance to jamming. Multiple transmissions can coexist in the same frequency band when using orthogonal spread spectrum codes. This is a key technology in cellular phone systems and is the basis of code division multiple access (CDMA).
Unfortunately, several complications are introduced by the distributed nature of ad hoc networks. First, the question arises, “which code to use and when to use it?” Synchronizing the codes transmitters use to those that receivers are using to receive is not trivial. Second, in a channel with only a finite number of codes available, the network needs to assign codes such that they are spatially distributed. In a dynamic network, keeping track of codes can be as complicated as keeping track of routes. Third, unlike CDMA cell phone systems, it is possible that a destination will be closer to an interfering transmitter than its source transmitter.
Even with a different spreading sequence the relative power of the interfering signals can raise the effective noise level of the channel such that the desired signal is lost. Finally, when codes are used, networks become packet sensing as opposed to carrier sensing. Receivers must synchronize with the transmitter from the beginning of the packet transmission or else the transmission appears as noise. To avoid interfering with an ongoing exchange at a destination a source must know that the destination is idle and ready to receive its transmission. The only way to be certain that the destination is idle is to monitor the exchanges to and from the destination. This is difficult, since it may be impossible to monitor an incoming transmission to this destination on account of separation from the distant source. Not knowing who this source is also prevents knowing the code that would be used in the destination's acknowledgement. Not sensing a destination is busy is no guarantee that it is idle.
There are four approaches to selecting codes: transmitter-based, receiver-based, pair-wise oriented, and common code shifted in time. In transmitter-based schemes a unique code is assigned to each transmitter. The problem with this approach is determining which transmitter's code a potential receiver should use at a given time.
In receiver-based schemes a unique code is assigned to each receiver. In this approach, there is no confusion at either the receiver or the transmitter as to which code to use but there is the question as to when the transmitter should start transmitting. Transmitting to a destination that is already receiving a packet from another source can interfere with that reception.
With transmitter-based codes the problem associated with an adjacent node interfering with a destination's reception is not as severe since it is precluded from using the same code.
In pair-wise oriented schemes unique codes are assigned to pairs of nodes. Pair-wise coding presents the same challenge to destinations as transmitter-based codes. Each potential destination needs to determine which code it should use in receiving.
Common code systems rely on the offset of the phase of codes used in transmissions that occur concurrently. The offsets may either occur randomly or be deliberate. In the latter case, the selection of the offset is no different than the selection of the spread spectrum code in the first three approaches. Additionally, despite the presence of an offset when using common codes there is still an increased likelihood that signals may interfere with each other. However, using a common code has an advantage in that it is the only approach that can support broadcast transmissions.
Proposed solutions to the problem of selecting codes normally involve the use of hybrid protocols. In one hybrid, all nodes monitor and contend using a common code but after the addresses of the source and destination are transmitted the transmitter uses a transmitter-based code to send the data packet. The destination knows which code to use since it receives the source address before the transition to the use of the transmitter-based code. In a second protocol, every node is assigned two codes, one to receive on and one to transmit on. When a node is idle it listens using its receive code. A source will use the receive code of the destination of a packet to send the source and destination address portion of the packet but will again transition to the source's transmit code to send the data portion.
Both approaches attempt to limit the time that another node may interfere with the exchange. In the first, other nodes will only interfere during the initial transmission of the addresses and in the second the potential interference occurs during the same period but is further reduced on account that interfering nodes must be transmitting to the same destination. The disadvantage of the second protocol over the first is its inability to broadcast packets.
The assignment of codes is also a problem in spread spectrum ad hoc networks. Normally there are a finite number of codes that must be distributed to a larger number of nodes. Random selection of codes may not assure the required physical separation of nodes using the same codes. Various algorithms have been developed for the assignment of codes. Most methods of assigning and distributing codes are associated with the hierarchical organization of networks.
Code assignment does not eliminate the unwanted interference from transmitters in close proximity to the destination end of other exchanges. In other words, the interfering source is closer to a destination than its intended source. Ideally, an access protocol would deliberately select transmitting nodes that do not interfere at the destinations.
Although there has been much work on the use of spread spectrum in ad hoc networks there are no protocols that completely integrate within a medium access control protocol the assignment of codes, the scheduling of a spatially distributed set of transmissions, and a method used by nodes to select codes for transmission and reception. In turn there are no methods that support the use of CDMA technology to transmit different messages from one node to many.
Routing protocols in ad hoc networks attempt to balance the reliability of routing information with the overhead that is required to obtain it. The objective is to obtain the best balance resulting in high end-to-end throughput in the network. Obviously, having very accurate routes will insure that a route can be found for a packet but may incur excessive routing overhead thus reducing the payload capacity of the network and in-turn reducing end-to-end throughput. Similarly, with less overhead the network may be able to support more payload but at the expense of greater delays and greater losses of packets and in-turn less end-to-end throughput. Additionally, most protocols are very dependent on the volatility of the network. Node mobility invariably increases the overhead required to support routing.
Routing protocols have been traditionally categorized as either link state or distance vector. Link state protocols are centralized routing protocols where individual nodes accumulate link state information and then calculate routes. Distance vector protocols are distributed protocols where neighbor routing information is used to construct routing tables.
Generally, when using link state information, no node has a vision of the complete network topology, only the next hop on a path to each destination. Each protocol reacts differently to link state changes. In the link state protocol all nodes must explicitly receive a packet indicating the change in the link state. Then that node can calculate new routes. In distance vector approaches, the effect of a change in a link state propagates through the network after the nodes that are ends of a changed link advertise a new routing table that uses different links. The effect of failed links may take a while to resolve and can result in route looping if some method is not applied to specifically preclude it from occurring. In either approach changes can result in a deluge of overhead traffic. In both the link state and distance vector approaches network volatility can result in so much overhead that network capacity collapses and network routes become inaccurate.
On account of the overhead in updating routing tables in ad hoc networks, modifications have been made to the basic link state and distance vector algorithms that attempt to preclude updates or to delay finding routes until they are needed. These approaches are broadly categorized as proactive and reactive protocols. Some distinguish these protocols as table driven versus on-demand routing protocols. In proactive protocols information about the network is sought continuously. The objective is to even out the routing overhead over time and to enable routes to be identified more quickly. Reactive protocols delay seeking routes until they are needed, thereby reducing overhead at the expense of responsiveness. Many ad hoc routing protocols have both proactive and reactive characteristics. A third approach to improving the basic protocols is to build a hierarchical organization of nodes that attempts to reduce the quantity of routing information necessary at individual nodes to identify routes. These are referred to as hierarchical routing approaches. Hierarchical routing protocols may still have proactive and reactive characteristics. A fourth approach is to use physical location in routing. Protocols that use location information either use this information to define a subset of the network's nodes within which to search for a route or directly use location information in calculating routes.
Several proactive routing schemes exist in conjunction with distance vector algorithms, most notably the Destination-Sequenced Distance-Vector (DSDV) routing protocol and the Wireless Routing Protocol (WRP). Both add additional information to the routing tables in order to prevent the creation of routing loops and to support faster convergence to valid routes after link changes. In DSDV the routing table includes a sequence number provided by a destination for each route. These destination sequence numbers are always even. Nodes will always use the route with the most recent sequence number and in the case of two routes with the same sequence number choose the route with the smaller metric. In the case of a route being identified as bad, a node advertises its routing table with the next odd sequence number for this route thereby also indicating an infinite metric. This message serves as a query to the destination to generate a new sequence number for identifying a new route. A node identifies a new route to a destination when it receives a route with a more recent sequence number. Loops are avoided since the protocol precludes a node from selecting a route based on an older sequence number. In WRP the routing tables include the addresses of predecessor nodes. A predecessor is the node that transmits a packet to a final destination. The objective of adding this additional information is to avoid looping. A node that identifies a link failure will select an alternate route through one of its neighbors that does not have the same predecessor node thus avoiding counting to infinity and looping. Additionally, with this predecessor information a node can trace back from each destination all hops that are taken from the source. Each node has the ability to verify that there are no loops in its routing tables and that routes do not use failed links thus enabling quicker convergence of the protocol.
Two proactive link state routing protocols have recently been proposed Optimized Link State Routing (OLSR) and Fisheye Routing. OLSR attempts to reduce the overhead of disseminating link state information by identifying a subset of nodes to broadcast link state information during the flooding process. The subset of nodes that relay link state information are referred to as multipoint relays (MPRs). Each node selects the MPRs for the link state information it relays. MPRs are selected to insure the broadest connectivity with the fewest MPRs. A node's set of MPRs must be able to reach all of its two-hop neighbors. Fisheye routing controls the frequency at which link state information is propagated through the network. Link state information is disseminated to distant nodes less frequently than it is disseminated to neighbors. The intuition behind the protocol is that changes in routes based on a distant destinations movements have only a small effect on the route near the source and that as the packet gets closer to the destination, nodes with more current information will take over the routing anyway. So these improvements to the basic link state routing protocol attempt to reduce the quantity of link state updates by either reducing the number of nodes disseminating them or by reducing the frequency of updates based on the need to receive them.
The most extensive research in ad hoc routing protocols has been in developing reactive protocols referred to as source initiated on-demand routing protocols. The general concept is pretty much to ignore routing until a route is needed. At that time, the source initiates some route searching mechanism to find the “best” route to the destination. The protocols differ in how much overhead is required to discover the route and the ability of the route to withstand or react to subsequent network changes. The simplest of the on-demand protocols is Ad Hoc On-Demand Distance Vector Routing (AODV). In AODV, nodes only retain routing information on routes over which they are actively participating. If a node needs a route, it attempts to discover one. The process involves a series of route request broadcasts that are flooded throughout the network. Three sequence numbers; source, broadcast ID, and destination, characterize the requests. Each node that receives a request notes the address of the node from which it first receives the request and either further broadcasts the request or responds with a unicast reply to the predecessor identifying that it can provide a path to the destination. If the request reaches the destination, the destination responds with the unicast reply. The distance of the final route received by the source depends on the manner in which the initial request progressed through the network. In the case of link failures, the node identifying the failure may reply back to the source that the route is no longer valid in which case the source executes a new search or it may attempt to do a repair locally by broadcasting its own route request packet. As can be seen the protocol relies on flooding to find a route but attempts several modifications to reduce the quantity of transmissions that are required.
The other on-demand routing protocols build upon the AODV concept. Dynamic Source Routing (DSR) requires nodes to retain routes that they have learned or overheard and then for these nodes to use this information to reduce the overhead of route discovery. If a node receives a route request for which it has a route it simply replies to the source. If a route is broken the node identifying the break either forwards the packet using an alternative route in its cache or it notifies the source, which then has the option of using another cached route or invoking the route discovery process. The Temporally Ordered Routing Algorithm (TORA) uses the route discovery process to build a directed acyclic graph (DAG) rooted at the destination. In such a graph all nodes point toward the most effective path to the destination. The advantage of this approach is that with link failure the algorithm provides an efficient method for the network to modify the DAG thus keeping a route to the destination. However, it is not effective at adding links except with a new discovery process.
Associativity-Based Routing (ABR) protocol uses locally gained information to give preference to the use of associated links in routes that are discovered. An associated link is a link between nodes that have a long-term association. This is measured by how long the two nodes have been within range of each other. It may occur when two nodes are not moving and are close to each other or if the nodes move in unison. The objective of this metric is to find routes with a greater expected longevity so that the route discovery process is used less often. When the destination receives several route requests it chooses the route that has the best associativity characteristics. ABR also has a very deliberate route reconstruction process. The specific process depends on where a link is lost. If the route fails near the destination, then the upstream node to the failed link attempts to find an alternate path. If unsuccessful, the responsibility is passed on to the next upstream node, and so on, until a new route is found or the process has backtracked half the distance of the original route. In the latter case the “pivot” node sends a route notification packet to the source so that it will reattempt the route discovery process.
A final example of the on-demand protocols is the Signal Stability-Based Adaptive Routing (SSA) protocol. SSA is similar in objective to ABR in that it attempts to identify greater longevity routes but it uses signal strength and location stability in its metrics for choosing the route. In the case of a link failure, the protocol requires the upstream node to notify the source of the error. The response is for the source to erase the route and to then invoke another discovery process. As can be seen, the on-demand routing protocols balance the quantity of overhead with the responsiveness of the route discovery process and the ability of the network to maintain valid routes without having to repeat the discovery effort. The trend in the improvement efforts is to use information that can be gained by individual nodes to support one or several of three objectives: find routes that are robust so there are fewer discovery efforts; leverage the information to fix failed routes; and, leverage the information to reduce the overhead of discovering routes.
Hierarchical routing protocols attempt to reduce the routing traffic by reducing the quantity of overhead required to create and maintain routes. Nodes are organized into clusters. The resolution of routing the table differs for routes within a cluster versus routes outside of clusters. Nodes have explicit routes to nodes within their own cluster but have limited understanding of the routes to nodes in other clusters except for the series of clusters the route follows to ultimately get to the destination. Some approaches identify certain leaders within each cluster to perform the route calculations in lieu of every node as a method to reduce routing overhead. Most proposals in this area focuses on the formation of clusters, the coordination of routes within clusters, the coordination of routes between clusters, and the maintenance of cluster organization. Clustering offers a new dimension to the complexity of routing in the sense that creating and maintaining the cluster organization adds overhead of its own. Several solutions have been suggested. They differ in whether clusters intersect, in the criteria used to form the clusters, and whether the clusters have leaders. The benefit of creating clusters is the reduction in routing overhead that results form reduced size routing tables, the reduced set of nodes participating in the routing algorithms, and a reduction in sensitivity to node mobility as this mobility is hidden within the cluster organization. The routing protocols themselves, however, remain very similar or identical to those discussed above. Hierarchical routing is a hybrid type of routing that combines the use of reactive and proactive routing protocols. Proactive protocols are used within the clusters and reactive routing is used between clusters. This hybrid use of protocols has also been suggested for flat networks in the Zone Routing Protocol (ZRP) as a method to reduce delay in the route discovery process without overloading the network with the overhead typical of the proactive protocols.
With the advent of the Global Positioning System (GPS) and other location technologies, physical location has increasingly been identified as a parameter in reducing routing overhead. Location is used in one of three ways. First, location can be used to define a smaller region within which to search for a route when using on-demand type protocols. One such protocol is Location-Aided Routing (LAR) where two different algorithms are suggested for defining a search region. The first is a simple box that is defined by the location of the source and a potential region where the destination may be located. In the second search algorithm requests are forwarded to packets based on their predicted distance to the destination. Both algorithms are effective at reducing overhead.
The second way location can reduce routing overhead is by reducing the number of routes that are tracked. An example of this type of protocol is LANMAR. Rather than maintaining routes to every node in a large network, nodes keep routes for a subset of nodes within its “scope” and then routes to several landmark nodes. Nodes not included in this list are associated with landmark nodes. Packets for distant nodes are first routed toward the destination's associated landmark and once the packet arrives at a node that has the destination within its scope, the packet is rerouted directly to the destination. As can be seen, this protocol accepts a less accurate route the more distance between the source and destination just as Fisheye routing.
Another example of this type of approach is the zone based hierarchical link state (ZHLS) routing protocol. In ZHLS spatial zones are mapped out and nodes use location information to identify their association with a zone. Within their physical zone, nodes use link state routing to route packets but packets destined for nodes in other zones are routed through intermediate zones rather than nodes. If a source does not know the location of a destination it queries each zone to find the destination.
The third approach is to use location explicitly in the calculation of routes. An example of this type of protocol is the Distance Routing Effect Algorithm for Mobility (DREAM). In DREAM, sources route packets to intermediate nodes in the direction of the last known location of the destination. When there is no node in the direction of the destination that is within range, the packet is flooded. Routing overhead is limited to that required to disseminate node locations. The rate of updates follows the philosophy of Fisheye routing. Nodes broadcast updates based on changes in location and assign a lifetime to these updates. Other nodes continue to forward these updates in broadcasts so long as the packet has not expired. In this manner distant nodes receive fewer updates. Also, less information must be disseminated in these updates since there are far fewer nodes than there are links.
With the exception of DREAM, all the protocols are based on the measured quality of links. The relative performance of current routing protocols is situation dependent. The distance vector and link state algorithms that perform so well for static networks are not suitable in highly dynamic networks. A significant difference between static networks and wireless networks is that the links themselves are not physical entities in wireless networks. Rather, the nodes and their distribution are the physical entities. Link availability and link capacity are transient being spatially and temporally dependent on the distribution of nodes. Therefore, it follows that node states are more relevant to the routing solutions than link states and distance vectors. Additionally, many of the objectives in wireless routing are node oriented such as location based services and energy conservation.
Quality of service (QoS) routing protocols built upon distributed access mechanism are few. Their effectiveness is questionable. The challenge is that most MAC protocols for ad hoc networks are based on temporally random attempts to differentiate who has access. (e.g. Aloha, Slotted Aloha, MACA, MACAW, FAMA, 802.11, HIPERLAN, etc.) Such access protocols prevent routing protocols from providing bandwidth and delay guarantees. It is not feasible to guarantee QoS when access to the channel at each hop occurs at random times. The typical approach to overcome this limitation is to improve the probability that packets that require some sort of QoS can gain access. This is accomplished at the MAC level by increasing the probability that these packets will attempt access first such as HIPERLAN, which provides a priority access scheme. But such priority access schemes are not effective in congested networks. So at the routing level, QoS routing either attempts to send packets through less congested regions of the network by creating routing metrics that favor stable and uncongested links. Each of these tasks is somewhat daunting.
Identifying less congested regions itself contributes to congestion. Like access protocols, the effectiveness of these routing protocols is very contingent on the network load. In addition, the measurement of link availability is based on passed qualities which may not be present when the service is attempted. The more appropriate approach is to reserve resources (i.e. links at specific times). A reservation approach is suggested which assumes a underlying Time Division Multiple Access (TDMA) MAC that is complemented with Code Division Multiple Access (CDMA). The gist of the protocol is to reserve TDMA slots along the path. It assumes away the near-far and hidden node problems on account of the use of CDMA (This is an assumption since no provisions are made to separate interfering transmitters from destinations. Even with the use of different codes hidden nodes may interfere if they are close to the destination.) Each destination along the path accepts a reservation from a source and agrees to listen to a slot on a periodic basis using the source's code. The initial access mechanism to the slots and the coordination of which codes to use are not described.
Mobile nodes in ad hoc networks frequently rely on batteries for energy and therefore have a finite lifetime. Conserving energy is therefore important to extending the lifetime of both individual nodes and the network. This is especially difficult in ad hoc networks since energy conserving actions must be made in a distributed manner. In fact, the continuous participation of the mobile nodes to create a fabric of connectivity is critical to the overall performance of the network. Typically, this results in a choice of either operating at peak performance at the expense of a shortly lived network or choosing sub optimum performance for network longevity. Additionally, most energy conserving protocols focus on the implementation of a single energy conserving approach.
Protocols may use four sets of mechanisms to reduce energy consumption: 1) help nodes enter low energy states; 2) choose routes that consume the least energy; 3) selectively use nodes based on their energy status; 4) reduce overhead.
Using low energy states has great potential for conserving energy since these state use less than a tenth of the energy used by radios when receiving or transmitting. The default state of nodes is receiving since signal processing is required to detect and to synchronize to an incoming signal. Entering a low energy state requires the node to cease sensing the channel and to stop participating in the network's activities. The objective of type 1 energy conserving protocols is to assist nodes that are not participating in data exchanges to enter a low energy state without degrading overall performance of the network. Proposed methods for managing nodes entering the doze state may be one of two kinds. In the first, nodes doze and then wakeup on a periodic basis according to network wide parameters. The 802.11 standard provides this kind of mechanism. The second requires the node desiring to doze to specifically coordinate a dozing cycle with another supporting node that agrees to act as a surrogate destination for the dozing node's traffic while it is dozing. The ETSI HIPERLAN standard uses this approach.
In both the 802.11 and HIPERLAN protocols, the decision to doze is initiated by the individual nodes desiring to conserve energy. In the ad hoc version of an 802.11 network, the node that first forms the network decides whether it permits energy conservation by establishing an “ATIM Period.” A node that desires to conserve energy may doze so long as it wakes each ATIM Period to listen for ad hoc traffic indication messages (ATIM). ATIMs are transmitted during a short window at the beginning of each ATIM period, called an ATIM Window. If the node wakes and hears an ATIM directed to itself, it acknowledges the ATIM and remains awake for the rest of the ATIM period prepared to receive traffic. If it receives no ATIM directed to itself, the node returns to the doze state at the conclusion of the ATIM window. Note that there is no method for a node's intent to doze to be disseminated. Other nodes assume this state after failing to transfer data through regular contention.
The energy conserving mechanism in HIPERLAN requires a node desiring to doze, a “p-saver,” to coordinate with another to serve as its surrogate, a “p-supporter”. As part of this coordination the two nodes agree to a period at which the p-saver will awaken to receive unicast messages and a period at which the p-supporter will transmit multicast messages. The p-supporter node collects transmissions intended for the p-saver and then attempts to forward them to the p-saver during the coordinated transmission periods.
HIPERLAN's approach is disconcerting since it does not make the dozing states known throughout the network. Nodes in ad hoc networks depend on each other to route and distribute packets to each other. The arrangement of having a surrogate node collect data for another may defeat many routing protocols. The p-supporter node may not be in a location to collect data from a relaying node in the opposite direction to the p-saver. Additionally, the p-saver may be a critical next hop in a route.
The critical deficiency of both the 802.11 and HIPERLAN techniques is that they do not account for the repercussions of a single node's decision to enter the doze state. These repercussions are more congestion as nodes attempt to send traffic to nodes that are dozing and complications for other protocols higher in the stack such as routing. To minimize these adverse effects, access protocols must be able to make dozing more predictable and to integrate the occurrence of dozing with the activities of the routing protocol.
Routing protocols conserve energy by identifying routes based on energy consumption. From the protocol perspective, energy is consumed in transmission and in reception. The energy consumed in transmission can vary based on the range between a source and its destination. This assumes that all nodes know each others' locations and that a source can adjust its transmission power to the minimum required for a successful exchange with a destination. The energy consumed in reception is constant. Due to the power law relation of energy consumed to the distance transmitted a route with more shorter hops may consume less energy than a route with fewer longer hops. It is possible for a route that used two equidistant hops to a destination would require as little as ⅛th the transmission energy of the direct one hop route. Routing protocols must also consider the energy consumed in each additional reception. So while the transmission energy decreases with more and shorter hops the reception energy increases. Therefore, calculating routes that consume the least energy is accomplished with either distance vector or link state routing algorithms together with a metric for links that combines the energy used in the transmission with the energy consumed in the reception. Building such a metric requires sharing information between the nodes at both ends of a link and some method for determining the power required to transmit across the link.
Routing protocols may prolong the lifetime of a network by preferring the use of nodes that are not energy constrained and by balancing the use of nodes that are energy constrained. One approach to solve this problem is Power-Aware Routing. It uses an energy cost metric for links that is obtained by weighting the energy consumption on the path by the energy reserve on each node of the path. This has a load balancing characteristic that steers traffic away from low energy nodes. Currently, there are no practicable uses of this metric either.
Current access methods further limit the practicability of using energy consumed and node lifetime as part of a routing metric. Both encourage more contentions in a network and in more congestion. This increase in congestion results in failed access attempts and, thus, a corresponding increase in energy consumption. It is believed that the decreased consumption of energy used in transmitting a packet is more than balanced by an increase in energy consumption to gain access for a net energy loss.
The challenge of implementing energy conservation mechanisms is their interlayer dependence. The success of a mechanism based on a MAC mechanism can greatly affect the routing protocol (e.g. dozing can remove potential routes) and vice versa (e.g. using shorter hops can increase congestion and preclude dozing). Energy conservation mechanisms must be integrated across layers. Such integration can be achieved only if the dozing methods are made known to the routing protocol and if the routing protocol does not cause congestion.
In view of the above, what would be truly useful is a protocol that can be used with ad hoc networks. Such a protocol would integrate medium access control and routing such that they provide quality of service, while conserving energy of individual mobile nodes, and while allowing maximum use of wireless channels minimizing collisions of concurrent communications.